import java.util.ArrayList;
import java.util.List;

public class Solution {

        public String convert(String s, int numRows) {
            if(numRows == 1) return s;
            List<StringBuilder> list = new ArrayList<>();
            int i = 0;
            int flag = -1;
            //初始化list中numsRows行
            for (int j = 0; j < numRows; j++) {
                list.add(new StringBuilder());
            }
            //遍历s中的每个字符
            for (char ch : s.toCharArray()){
                list.get(i).append(ch);
                //若遇到Z字形的转折点
                if(i == 0 || i == numRows - 1){
                    flag = -flag;
                }
                //更新下次ch所在行的索引
                i += flag;
            }
            StringBuilder ret = new StringBuilder();
            //合并所有的行
            for(StringBuilder sb: list){
                ret.append(sb);
            }
            return ret.toString();
        }

        public int countSubstrings(String s) {
                //思想：遍历字符串，
                //利用双指针法，从中心位置开始拓展, 中心位置可以是一个字符,也可能是两个字符
                //因为回文字符串可能是奇数个字符也可能是偶数个字符
                int n = s.length();
                char[] ch = s.toCharArray();
                int ret = 0;
                for(int i = 0; i < n; i++){
                    for(int j = i; j <= i +1;j ++){
                        int left = i;
                        int right = j;
                        while(left >= 0 && right < n && ch[left--] == ch[right++]){
                            ret++;
                        }
                    }
                }
            return ret;
        }
}
